package algorithm.sort;

/**
 * 冒泡排序(稳定的排序算法)
 *
 * @author: fengpeng
 * @date: 2019/1/17  下午9:33
 */
public class BubbleSort<T extends Comparable<? super T>> {

    /**
     * 冒泡排序(普通版本)
     *
     * @param list 待排序数字
     */
    public void bubbleSortProcess1(T[] list){
        int len = list.length;
        //统计遍历执行次数
        int t = 0;
        for (int i =0;i < len-1; i++){
            for (int j = 0;j<len-1-i;j++){
                if (list[j].compareTo(list[j+1])>0){
                    T temp = list[j+1];
                    list[j+1]= list[j];
                    list[j] = temp;
                }
            }
            t++;
        }
        System.out.println("**********"+t+"*****************");
    }

    /**
     * 冒泡排序(改进版本)
     * 如果在一次比较中，如果没有发生位置替换，
     * 则说明此时数组已经有序，无需进行后面遍历替换操作
     *
     * @param list 待排序数字
     */
    public  void bubbleSortProcess2(T[] list){
        int len = list.length;
        //统计遍历执行次数
        int t = 0;
        boolean flag = true;
        for (int i =0;i < len-1 && flag ; i++){
            flag = false;
            for (int j = 0;j<len-1-i;j++){
                if (list[j].compareTo(list[j+1])>0){
                    T temp = list[j+1];
                    list[j+1]= list[j];
                    list[j] = temp;
                    flag = true;
                }
            }
            t++;
        }
        System.out.println("**********"+t+"*****************");
    }

    public static void main(String[] args){
        BubbleSort bubbleSort = new BubbleSort<Integer>();
        //Integer[] list = new Integer[]{49,23,199,43,12,200};
        Integer[] list = new Integer[]{200,199,12,23,43,49};
        bubbleSort.bubbleSortProcess1(list);
        bubbleSort.bubbleSortProcess2(list);
        for (Integer i : list) {
            System.out.print(i +" ");
        }
    }

}
